package com.wenlin.myproduction.util;

/**
 * @author 文琳
 * @Email 377979485@qq.com
 * @desc 给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。
 * <p>
 * 你可以删除 s 中任意数目的字符，使得 s 平衡 。我们称 s 平衡的 当不存在下标对 (i,j) 满足 i < j 且 s[i] = 'b' 同时 s[j]= 'a' 。
 * <p>
 * 请你返回使 s 平衡 的 最少 删除次数。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "aababbab"
 * 输出：2
 * 解释：你可以选择以下任意一种方案：
 * 下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
 * 下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。
 * 示例 2：
 * <p>
 * 输入：s = "bbaaaaabb"
 * 输出：2
 * 解释：唯一的最优解是删除最前面两个字符。
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 105
 * s[i] 要么是 'a' 要么是 'b'​ 。​
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @time 2022-08-16 星期二 18:09
 */
public class MinimumDeletionsUtil {
    public int minimumDeletions(String s) {
        //根据题意，检查时只要不出现ba就行
        //第一次每一次都删除b，记录删除次数和删除位置。然后从最后一个开始回溯，如果删除a，检查步数是否需要增加。
        int times = 0;
        System.out.println("初始s = " + s);
        String trimStr = getTrimStr(s);
        int index;
        if (isALess(trimStr)) {//a更少，优先删a，从右边找
            index = lastBaIndex(s);
        } else {//b更少，优先删b，从左边找
            index = firstBaIndex(s);
        }
        while (index > -1) {
            trimStr = getTrimStr(s);
            if (isALess(trimStr)) {//去除左侧的所有a和右侧所有b的中间部分（b……a）如果a少就删a，b少就删b
                s = s.substring(0, index + 1) + s.substring(index + 2);//删除a
                System.out.println("删除a");
            } else {
                s = s.substring(0, index) + s.substring(index + 1);//删除b
                System.out.println("删除b");
            }
            System.out.println("s = " + s);
            times++;
            trimStr = getTrimStr(s);
            if (isALess(trimStr)) {//a更少，优先删a，从右边找
                index = lastBaIndex(s);
            } else {//b更少，优先删b，从左边找
                index = firstBaIndex(s);
            }
        }
        return times;
    }

    /**
     * 去除左侧的所有a和右侧的所有b剩下待处理的部分
     *
     * @param s 字符串
     * @return 所求
     */
    private String getTrimStr(String s) {
        while (s.startsWith("a") || s.endsWith("b")) {
            if (s.startsWith("a")) {
                s = s.substring(1);
            }
            if (s.endsWith("b")) {
                s = s.substring(0, s.length() - 1);
            }
        }
        return s;
    }

    /**
     * 返回a是不是比b少
     *
     * @param s 字符串
     * @return 所求
     */
    private boolean isALess(String s) {
        int a = 0;
        int b = 0;
        for (int i = 0; i < s.length(); i++) {
            String str = s.substring(i, i + 1);
            if (str.equals("a")) {
                a++;
            } else if (str.equals("b")) {
                b++;
            }
        }
        System.out.println("a还剩" + a);
        System.out.println("b还剩" + b);
        return a < b;
    }

    /**
     * 返回找到的第一个ba
     *
     * @param s 字符串
     * @return 所求
     */
    private int firstBaIndex(String s) {
        for (int i = 0; i < s.length() - 1; i++) {
            String str = s.substring(i, i + 2);
            if (str.equals("ba")) {
                System.out.println("第一个ba.index = " + i);
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回找到的最后一个ba
     *
     * @param s 字符串
     * @return 所求
     */
    private int lastBaIndex(String s) {
        for (int i = s.length() - 2; i >= 0; i--) {
            String str = s.substring(i, i + 2);
            if (str.equals("ba")) {
                System.out.println("最后一个ba.index = " + i);
                return i;
            }
        }
        return -1;
    }
}
